package cn.edu.jxau.test;

import java.util.ArrayList;
import java.util.List;

/**
 * 有向图
 * 
 * @author 付大石
 */
public class DirectedGraph {

    public static void main(String[] args) {
        
        DirectedGraph g = new DirectedGraph(13);
        g.addEdge(4,2);
        g.addEdge(2,3);
        g.addEdge(3,2);
        g.addEdge(6,0);
        g.addEdge(0,1);
        g.addEdge(2,0);
        g.addEdge(11,12);
        g.addEdge(12,9);
        g.addEdge(9,10);
        g.addEdge(9,11);
        g.addEdge(8,9);
        g.addEdge(10,12);
        g.addEdge(11,4);
        g.addEdge(4,3);
        g.addEdge(3,5);
        g.addEdge(7,8);
        g.addEdge(8,7);
        g.addEdge(5,4);
        g.addEdge(0,5);
        g.addEdge(6,4);
        g.addEdge(6,9);
        g.addEdge(7,6);
        
        System.out.println(g);
        System.out.println();
        System.out.println();
        System.out.println(g.reverse());
    }

    /**
     * 顶点数
     */
    private int v;

    /**
     * 边数
     */
    private int e;

    /**
     * 邻接表
     */
    private List<Integer>[] adj;

    public DirectedGraph(int v) {

        this.v = v;
        adj = new List[v];
        for (int i = 0; i < adj.length; i++) {
            adj[i] = new ArrayList<>();
        }
    }

    /**
     * 获取顶点数
     * @return
     */
    public int v() {
        return v;
    }

    /**
     * 获取边数
     * @return
     */
    public int e() {
        return e;
    }

    /**
     * 增加一条有向边
     * @param v
     * @param w
     */
    public void addEdge(int v, int w) {

        validateVertex(v);
        validateVertex(w);
        adj[v].add(w);
        e++;
    }

    /**
     * 获取从顶点v出发的顶点
     * @param v
     * @return
     */
    public Iterable<Integer> adj(int v) {

        validateVertex(v);
        return adj[v];
    }

    private void validateVertex(int v) {
        if (v < 0 || v >= this.v) {
            throw new IllegalArgumentException("参数指定的顶点不存在，v=" + v);
        }
    }

    /**
     * 返回该有向图的反向图
     * @return
     */
    public DirectedGraph reverse() {

        int v = v();
        DirectedGraph reverse = new DirectedGraph(v);
        for (int i = 0; i < v; i++) {
            for (int w : adj(i)) {
                reverse.addEdge(w, i);
            }
        }
        return reverse;
    }

    @Override
    public String toString() {

        StringBuilder builder = new StringBuilder();
        builder.append("v:").append(v()).append("\te:").append(e());
        builder.append("\n");
        int v = v();
        for (int i = 0; i < v; i++) {
            builder.append(i).append("\t|\t");
            for (int j : adj(i)) {
                builder.append(j).append("\t");
            }
            builder.append("\n");
        }
        builder.deleteCharAt(builder.length() - 1);
        return builder.toString();
    }
}
